package leetcode.algorithms.贪心算法;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * 初始化所有孩子的糖果数量为1，因为相邻的孩子，分数高的糖果数比分数低的糖果数多。
 * 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的
 * 糖果数加 1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数
 * 不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。通过这两次遍历，
 * 分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一
 * 侧的大小关系。
 *
 */
public class BCode135 {

    public static int candy(int[] ratings) {
        int[] nums = new int[ratings.length];
        Arrays.fill(nums,1);

        for(int i=1;i < ratings.length; i++){
            if(ratings[i] > ratings[i-1]){
                nums[i] = nums[i-1]+1;
            }
        }

        for(int i = ratings.length-1; i>0;i--){
            if(ratings[i-1] > ratings[i]){
                nums[i-1] = Math.max(nums[i-1],nums[i]+1);
            }
        }
        return IntStream.of(nums).sum();
    }

    public static void main(String[] args) {
        int[] ratings = new int[]{1,0,2};
        System.out.println(candy(ratings));
    }
}
